#include<stdio.h>
typedef struct four
{
    int quan;
    int fumu;
    int lchild;
    int rchild;
}four;
void chushihua(four*hfm,int num,int x)
{
    int i=0;
    int qq;
    for(i=0;i<x;i++)//初始化前x个的权
    {
        printf("输入结点权的大小\n");
        scanf("%d",&qq);
        hfm[i].quan=qq;
        hfm[i].fumu=-1;
        hfm[i].lchild=-1;
        hfm[i].rchild=-1;
    }
    for(i;i<num;i++)//初始化所有的权
    {
        hfm[i].quan=-1;
        hfm[i].fumu=-1;
        hfm[i].lchild=-1;
        hfm[i].rchild=-1;
    }
}
void find(four*hfm,int xx,int *s1,int *s2)
{
    int i=0;
    int min;
    while(hfm[i].fumu!=-1&&i<xx)
    {
        i++;
    }
    *s1=i;
    min=hfm[i].quan;
    for(i+1;i<xx;i++)
    {
        if(hfm[i].fumu==-1&&min>hfm[i].quan)
        {
            min=hfm[i].quan;
            *s1=i;
        }
    }
    i=0;
    while(hfm[i].fumu!=-1&&i<xx||i==(*s1))
    {
        i++;

    }
    *s2=i;
    min=hfm[i].quan;
    for(i=i+1;i<xx;i++)
    {
        if(hfm[i].fumu==-1&&min>hfm[i].quan&&i!=(*s1))
        {
            min=hfm[i].quan;
            *s2=i;
        }
    }

}
void chuangjian(four*hfm,int num,int x)
{
    int xx=x;
    x=x-1;
    while(x--)//只需结合n-1次
    {
        int s1;
        int s2;//最小和次小权的下标
        find(hfm,xx,&s1,&s2);
        hfm[xx].quan=hfm[s1].quan+hfm[s2].quan;
        hfm[xx].fumu=-1;
        hfm[s1].fumu=xx;
        hfm[s2].fumu=xx;
        hfm[xx].lchild=s1;
        hfm[xx].rchild=s2;
        xx++;
    }

}
void print(four*hfm,int num)
{
    int i=0;
    for(i=0;i<num;i++)
    {
        printf("%d %d %d %d",hfm[i].quan,hfm[i].fumu,hfm[i].lchild,hfm[i].rchild);
        printf("\n");
    }
}
int main()
{
    int x;
    printf("输入叶子结点的个数\n");
    scanf("%d",&x);
    int num=2*x-1;//总共的结点数
    four *hfm=(four*)malloc(sizeof(four)*num);
    chushihua(hfm,num,x);
    chuangjian(hfm,num,x);
    print(hfm,num);
    return 0;
}
